Label Propagation Algorithm Based on Over-Relaxation Iteration
GE Fang1, GUO Youqiang1, WANG Nian2
1.Department of Computer Science and Technology, Bengbu University, Bengbu 233030 2.Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education,Anhui University, Hefei 230039
Abstract：Aiming at the problem in the label propagation algorithm, over-relaxation iteration is introduced to solve the optimization problem of label sequence and an improved label propagation algorithm based on over-relaxation iteration (ORLP) is presented. The known samples are labeled with positive and negative labels and the label information of unknown samples is predicted by learning the classification between neighbor points. Meanwhile, the label information of initial labeled samples is reserved in each iteration to guide the next label propagation process. In addition, grounded on over-relaxation iteration, the label propagation formula of ORLP is inferred and the convergence of label sequence is proved simultaneously. Thus, the convergence solution of label sequence is obtained. The experimental results show that the ORLP has higher classification accuracy and convergence speed.
[1] 李昆仑,曹 铮,曹丽苹,等.半监督聚类的若干新进展.模式识别与人工智能, 2009, 22(5): 735-742.(LI K L, CAO Z, CAO L P, et al. Some Developments on Semisupervised Clustering. Pattern Recognition and Artificial Intelligence, 2009, 22(5): 735-742.) [2] CHAPELLE O, SCHLKOPF B, ZIEN A. Semisupervised Learning. Cambridge, USA: MIT Press, 2006. [3] BALCAN M F, BLUM A. A Discriminative Model for Semisupervised Learning. Journal of the ACM, 2008, 57(3): 517-527. [4] KOBAYASHI T. KernelBased Transition Probability toward Similarity Measure for Semisupervised Learning. Pattern Recognition, 2014, 47(5): 1994-2010. [5] ZHU X J, GHAHRAMANI Z B, LAFFERTY J D. Semisupervised Learning Using Gaussian Fields and Harmonic Functions // Proc of the 20th International Conference on Machine Learning. Washington, USA, 2003: 912-919. [6] ZHU X J. Semisupervised Learning with Graphs. Ph.D Dissertation. Pittsburgh, USA: Carnegie Mellon University, 2005. [7] ZHOU D Y, BOUSQUET O, LAL T N, et al. Learning with Local and Global Consistency // THRUN S, SAUL L K, SCHLOKOPF B, eds. Advances in Neural Information Processing Systems 16. Cambridge, USA: MIT Press, 2004: 321-328. [8] WANG J D, WANG F, ZHANG C S, et al. Linear Neighborhood Propagation and Its Applications. IEEE Trans on Pattern Analysis and Machine Intelligence, 2009, 31(9): 1600-1615. [9] TANG J H, HUA X S, QI G J, et al. Video Annotation Based on Kernel Linear Neighborhood Propagation. IEEE Trans on Multimedia, 2008, 10(4): 620-628. [10] TANG J H, HUA X S, WANG M, et al. Correlative Linear Neighborhood Propagation for Video Annotation. IEEE Trans on Systems, Man, and Cybernetics(Cybernetics), 2009, 39(2): 409-416. [11] BAI X, YANG X W, LATECKI L J, et al. Learning ContextSensitive Shape Similarity by Graph Transduction. IEEE Trans on Pattern Analysis and Machine Intelligence, 2010, 32(5): 861-874. [12] HE M, LENG M W, LI F, et al. A Node Importance Based Label Propagation Approach for Community Detection // LAMBRIX P, HYVNEN E, BLOMQVIST E, et al., eds. Knowledge Engineering and Management. Cambridge, USA: MIT Press, 2014: 249-257. [13] FU B, WANG Z H, XU G D, et al. Multilabel Learning Based on Iterative Label Propagation over Graph. Pattern Recognition Letters, 2014, 42: 85-90. [14] CAO L J, JI R R, LIU W, et al. Weakly Supervised Codebook Learning by Iterative Label Propagation with Graph Quantization. Signal Processing, 2013, 93(8): 2274-2283. [15] PAPADOPOULOS S, KOMPATSIARIS Y, VAKALI A, et al. Community Detection in Social Media: Performance and Application Considerations. Data Mining and Knowledge Discovery, 2012, 24(3): 515-554. [16] SAAD Y. Iterative Methods for Sparse Linear Systems. 2nd Edition. Boston, USA: Society for Industrial & Applied Mathematics, 2003.
2016, Vol. 29 
